package algorithms.strings

/**
 * [Morgan and a String](https://www.hackerrank.com/challenges/morgan-and-a-string)
 */
// Complete the morganAndString function below.
fun morganAndString(a: String, b: String): String {
    val lenA = a.length
    val lenB = b.length
    var indexA = 0
    var indexB = 0
    val stringBuilder = java.lang.StringBuilder(a.length + b.length)
    val charArrayA = Array(lenA + 1) { 'z' }
    val charArrayB = Array(lenB + 1) { 'y' }

    a.forEachIndexed { index, c -> charArrayA[index] = c }
    b.forEachIndexed { index, c -> charArrayB[index] = c }

    var endA = 0
    var endB = 0
    var endCharA = 'z'
    var endCharB = 'y'

    fun splitCharGroup(s: String, start: Int): Int {
        if (start >= s.length) {
            return start
        }
        var preChar = s[start]
        var curChar: Char
        for (i in start + 1 until s.length) {
            curChar = s[i]
            if (curChar < preChar) {
                return i
            }
            preChar = curChar
        }
        return s.length
    }

    fun compareSubString(i: Int, j: Int): Boolean {
        var ii = i
        var ij = j
        var charA: Char = charArrayA[ii]
        var charB: Char = charArrayB[ij]

        while ((charA == charB) && ii < lenA && ij < lenB) {
            ii++
            ij++
            charA = charArrayA[ii]
            charB = charArrayB[ij]
        }

        return charA < charB
    }

    fun mergeString() {
        var charA: Char = charArrayA[indexA]
        var charB: Char = charArrayB[indexB]

        while (indexA < endA && indexB < endB) {
            when {
                charA < charB -> {
                    indexA++
                    stringBuilder.append(charA)
                    charA = charArrayA[indexA]
                }
                charA > charB -> {
                    indexB++
                    stringBuilder.append(charB)
                    charB = charArrayB[indexB]
                }
                else -> {
                    if (charA != endCharA && charB != endCharB) {
                        indexA++
                        indexB++
                        stringBuilder.append(charA)
                        stringBuilder.append(charB)
                        charA = charArrayA[indexA]
                        charB = charArrayB[indexB]
                    } else {
                        stringBuilder.append(charA)
                        if (compareSubString(indexA, indexB)) {
                            indexA++
                            return
                        } else {
                            indexB++
                            return
                        }
                    }
                }
            }
        }

    }

    while (indexA < lenA && indexB < lenB) {
        if (indexA >= endA) {
            endA = splitCharGroup(a, indexA)
            endCharA = charArrayA[endA - 1]
        }
        if (indexB >= endB) {
            endB = splitCharGroup(b, indexB)
            endCharB = charArrayB[endB - 1]
        }

        mergeString()
    }

    while (indexA < lenA) {
        stringBuilder.append(a[indexA++])
    }
    while (indexB < lenB) {
        stringBuilder.append(b[indexB++])
    }

    return stringBuilder.toString()
}